The present invention relates to a decoding apparatus and method for encoded data of still images and moving images.
Conventionally, a scheme using an entropy coding technique using a variable-length code is well known as one compression coding technique of still images and moving images. This technique is also adopted in JPEG (Joint Photographic Expert Group) as an international standard. In recent years, especially, many hardware implementation means using a Huffman code table as a variable-length code have been proposed. Such prior art will be explained below.
A conventional decoding apparatus comprises a shift means which comprises a circuit capable of shifting input encoded data for respective bits, a decoder for obtaining the code length and frequency of generation of a head code output from the shift means by comparing the encoded data output from the shift means and a pre-stored minimum or maximum code word of each code length, a symbol memory for storing decoded data (symbol data) in the order of frequency of generation, an additional bit processor for executing an additional bit process, and a shift amount select means for controlling a shift amount of the shift means.
The shift amount select means selects, as the shift amount of the shift means, the code length obtained by the decoder in an odd cycle, and an additional bit length output from the symbol memory in an even cycle. In this example, the throughput of the decoding process is always 0.5 symbols/cycle. In addition, the following technique for improving the throughput of the decoding process is known.
In this technique, a decoding apparatus comprises two different decoders, and a first decoder executes the same process in the aforementioned decoder. On the other hand, a second decoder pre-stores code words with high frequencies of generation and symbol data corresponding to these code words, and outputs symbol data in one cycle for a code word with a high frequency of generation.
For other code words, the first decoder generates an address of the symbol memory, and outputs symbol data output from the symbol memory in the next cycle as decoded data. According to this example, a throughput of a maximum of 1 symbol/cycle can be obtained.
In order to realize a high-speed decoding process, a specific decoding means must be implemented as hardware and the circuit must be operated at high frequency. However, the conventional apparatus suffers the following problems.
Conventionally, since an additional bit processing means is unknown in the decoding process, it is difficult to attain hardware implementation. Especially, when a process is done at the throughput of a maximum of 1 symbol/cycle, since the additional bit processor must at least cope with this processing rate, a hardware implementation means of the additional bit processor is very important upon realizing a high-speed circuit.
When two different blocks (second decoder and symbol memory) output decoded data depending on input encoded data, since their latencies (execution times) are different, the input timings of symbol data to a selector deviate from each other. Hence, control that considers this timing deviation is required, resulting in complicated control.
It is hard to implement a pipeline process. Even if code lengths corresponding to the code words stored in the second decoder are stored in advance and a code length corresponding to a selected code word is shifted out from the shift means in one cycle to solve the aforementioned problem, since the output from the decoding apparatus is one cycle, an arithmetic operation for the decoding process, e.g., an additional bit arithmetic operation must be done in one cycle, and it is difficult to realize a pipeline structure in synchronous circuit design.
In order to achieve efficient, high-speed processes, the processing unit must be shifted for each encoded data. However, conventionally, the shift amount control of the input means to the decoding apparatus is unknown.
FIG. 11 shows the arrangement of a variable-length decoding apparatus as prior art 1. This decoding apparatus comprises a shift-out means (to be referred to as xe2x80x9cshiftxe2x80x9d hereinafter) 1201 that comprises a circuit capable of shifting input encoded data for respective bits, a decoder 1203 for obtaining the code length and frequency of generation of a head code output from the shift 1201 by comparing the encoded data output from the shift 1201 and a minimum or maximum code word of each code length, which is stored in advance, a symbol memory 1205 for storing decoded data (symbol data RRRR/SSSS) in the order of frequency of generation, an additional bit processor 1202 for executing an additional bit process, and a shift amount select means 1204 for controlling the shift amount of the shift 1201.
The shift amount select means 1204 selects, as the shift amount of the shift 1201, the code length obtained by the decoder 1203 in an odd cycle, and an additional bit length output from the symbol memory 1205 in an even cycle.
FIG. 12 shows the arrangement of prior art 2 which can improve the throughput of the decoding process in addition to the decoding apparatus of prior art 1. In this prior art, a high-speed symbol decoder 1352 executes a high-speed decoding process of a plurality of selected symbols, and a symbol decoder 1353 decodes other symbols. As an example of a select means of symbols to be decoded by the high-speed symbol decoder 1352, a plurality of symbols in descending order of frequency of generation, or symbols with zero runlength may be selected.
A characteristic feature of prior art 2 lies in that priority is given to the decoding process of the high-speed symbol decoder 1352. If input encoded data hits a code word corresponding to a symbol registered in the high-speed symbol decoder 1352, the decoding result of the high-speed symbol decoder 1352 is preferentially selected as an output.
FIG. 13 shows prior art 3 as a technique for further improving the throughput of prior art 2. A variable-length decoding apparatus according to prior art 3 comprises a 1-code word decoder 1403 for decoding a head code word, and a 2-successive code word decoder 1402 capable of decoding a successive sequence of two ode words from the head with high frequency of generation, and is characterized in that priority is given to the 2-successive code word decoder 1402. If a hit has occurred in the 2-successive code word decoder 1402, since two code words can be decoded at one time, the throughput can be further improved.
As the encoded data sizes of still images and moving images increase, the required processing performance for an encoding processing apparatus becomes considerably high. Especially, since the variable-length decoding apparatus must decode a variable-length code, it is very difficult to improve the throughput. For this reason, various solutions have been proposed so far, but the following problems remain unsolved.
The throughput varies depending on the hit ratio of the high-speed symbol decoder 1352. Even if all data hit, the performance of a maximum of only one symbol per decoding sequence is obtained. This throughput is insufficient in consideration of the performance required for a variable-length decoding apparatus in the future. When the symbol decoder 1353 can decode in one cycle, an effect obtained upon adopting a parallel arrangement with the high-speed symbol decoder 1532 is lost. Such problem occurs when a table that stores symbol data as a decoding result comprises an asynchronous RAM or hardwired. The recent advance of semiconductor techniques allows to operate at higher clock frequency even if the circuit arrangement remains the same, and a conventional circuit which processes in two cycles can now process in one cycle.
As in prior art 2, the throughput varies depending on the hit ratio of the 2-successive code word decoder 1402, and the performance of a maximum of two code words per decoding sequence can be obtained. However, this technique can be implemented in Huffman coding used in MPEG, but cannot be applied to JPEG. This is because variable-length encoded data in JPEG is made up of a Huffman code word and additional bit. For this reason, the 2-successive code word decoder 1402 cannot decode if it simply compares two successive code words with input encoded data, and must consider an additional bit corresponding to a head code word to be decoded by the 1-code word decoder 1403.
It is an object of the present invention to implement a variable-length decoding apparatus that can hardly achieve high-speed operations as a pipeline process consisting of three stages by synchronous design using a synchronous RAM. It is another object of the present invention to allow two different decoders to share an additional bit processing circuit and decoded data storage means, and to improve the throughput while minimizing an increase in circuit scale.
In order to achieve the above object, a variable-length decoding apparatus of the present invention comprises the following arrangement.
That is, a variable-length decoding apparatus for decoding encoded data, comprises:
shift means for shifting out a code word and an additional bit corresponding to the code word of input encoded data for each cycle;
a symbol memory for storing decoded data corresponding to a plurality of N code words contained in the input encoded data;
first decode processing means for generating an address of the symbol memory, a code length, and an additional bit length for each of Nt code words fewer than the N code words of the code words input from the shift means;
second decode processing means for generating a code length and an address of the symbol memory for each of the N code words;
address select means for selecting one of the two addresses of the symbol memory input from the first and second decode processing means;
first additional bit processing means for shifting bits of the output from the shift means to the left by the code length input from one of the first and second decode processing means;
second additional bit processing means for shifting bits of the output from the first additional bit processing means to the right by an amount corresponding to symbol data output from the symbol memory; and
operation control means for outputting a shift amount to the shift means.
It is still another object of the present invention to provide a decoding apparatus and method, which can be applied to decoding of JPEG and MPEG encoded data, and can obtain a high throughput.
In order to achieve the above object, for example, one decoding apparatus of the present invention comprises the following arrangement.
That is, a decoding apparatus for decoding variable-length encoded data, and outputting symbol data, comprises:
first shift-out means for shifting out a code word of input encoded data in accordance with shift amount select means, and outputting a head code word and subsequent encoded data;
first decode means for decoding the head code word output from the first shift-out means, and generating first symbol data and a bit length N (N is an integer) of the code word;
second shift-out means for further shifting the head code word and subsequent encoded data output from the first shift-out means on the basis of the bit length N output from the first decode means, and outputting a subsequent first code word; and
second decode means for, when the subsequent first code word output from the second shift-out means belongs to one of a code word group obtained by selecting in advance some of all code words which form the encoded data, generating second symbol data as a decoding result and a bit length M (M is an integer) of the code word,
wherein the shift amount select means determines, as a shift amount of the first shift-out means, a shift amount by selecting a bit length N+M obtained by adding the bit lengths N and M when the second decode means generates the second symbol data, and by selecting the bit length N in other cases.
In the above arrangement, a maximum of two symbol data can be output in one cycle, and the throughput can be remarkably improved compared to the prior art.
Other features and advantages of the present invention will be apparent from the following description taken in conjunction with the accompanying drawings, in which like reference characters designate the same or similar parts throughout the figures thereof.